/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
//方法一：哈希表映射
// class Solution {
// public:
//     Node* copyRandomList(Node* head) {
//         if(!head) return nullptr;
//         Node* cur=head;
//         unordered_map<Node*,Node*> hash;
//         while(cur)
//         {
//             Node* node=new Node(cur->val);
//             hash[cur]=node;
//             cur=cur->next;
//         }
//         cur=head;
//         while(cur)
//         {
//             hash[cur]->next=hash[cur->next];
//             hash[cur]->random=hash[cur->random];
//             cur=cur->next;
//         }
//         return hash[head];
//     }
// };


//方法二，先组合再拆分
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(head==nullptr) return nullptr;
        Node* cur=head;
        while(cur)
        {
            Node* curNew=new Node(cur->val);
            curNew->next=cur->next;
            cur->next=curNew;
            cur=curNew->next;
        }
        cur=head;
        while(cur)
        {
            if(cur->random!=nullptr)
                cur->next->random=cur->random->next;
            cur=cur->next->next;
        }

        cur=head->next;
        Node* pre=head,*res=head-> next;
        while(cur->next)
        {
            pre->next=pre->next->next;
            cur->next=cur->next->next;
            pre=pre->next;
            cur=cur->next;
        }

        pre->next=nullptr;
        return res;
    }
};
